package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-10 20:38
 **/
public class LeetCode215 {

    //基于堆排序的选择方法
    public int findKthLargest(int[] nums, int k) {
        sort(nums, nums.length, k);
        return nums[0];
    }

    static void sort(int[] nums, int heapSize, int k) {
        buildMaxHeap(nums, heapSize);

        while (heapSize > nums.length - k + 1) {
            swap(nums, 0, --heapSize);
            maxHeapify(nums, 0, heapSize);
        }
    }

    static void buildMaxHeap(int[] nums, int heapSize) {
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            maxHeapify(nums, i, heapSize);
        }
    }

    static void maxHeapify(int[] nums, int i, int heapSize) {
        int a = 2 * i + 1;
        int b = 2 * i + 2;
        int max = i;
        int len = nums.length;
        if (a < heapSize && nums[max] < nums[a]) {
            max = a;
        }

        if (b < heapSize && nums[max] < nums[b]) {
            max = b;
        }

        if (max != i) {
            swap(nums, i, max);
            maxHeapify(nums, max, heapSize);
        }
    }

    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //快速选择
    /*public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    int quickSelect(int[] nums, int l, int r, int k) {
        if (l == r) {
            return nums[l];
        }

        int i = l;
        int j = r;
        int mid = i + j >> 1;
        int pivot = nums[mid];
        while (i <= j) {
            while (i <= j && nums[i] > pivot) {
                i++;
            }

            while (i <= j && nums[j] < pivot) {
                j--;
            }

            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j--;
            }
        }

        if (l + k - 1 <= j) {
            return quickSelect(nums, l, j, k);
        }

        if (l + k - 1 >= i) {
            return quickSelect(nums, i, r, k - i + l);
        }

        return nums[j + 1];
    }*/

    //排序
    /*public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }*/

}
